package com.camus.datastructureandalgorithm.algorithm.sort;

/**
 * @author jie.deng
 * 归并排序
 */
public class MergeSortArray implements SortArray {

    @Override
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        // 递推公式: merge_sort(p...r) = merge(merge_sort(p...r), merge_sort(q...r))
        // 终止条件: p>=r不用再继续分解

        return sortArray(nums, 0, nums.length - 1);
    }

    private int[] mergeArr(int[] lArr, int[] rArr) {
        if (lArr == null || lArr.length == 0) {
            return rArr;
        }
        if (rArr == null || rArr.length == 0) {
            return lArr;
        }

        int lLen = lArr.length;
        int rLen = rArr.length;
        int[] mergeArr = new int[lLen + rLen];

        int l = 0, r = 0, m = 0;
        while (l < lLen && r < rLen) {
            if (lArr[l] > rArr[r]) {
                mergeArr[m++] = rArr[r++];
            } else {
                mergeArr[m++] = lArr[l++];
            }
        }
        while (r < rLen) {
            mergeArr[m++] = rArr[r++];
        }
        while (l < lLen) {
            mergeArr[m++] = lArr[l++];
        }

        return mergeArr;
    }

    private int[] sortArray(int[] nums, int lIdx, int rIdx) {
        if (lIdx > rIdx) {
            return new int[0];
        }
        if (lIdx == rIdx) {
            return new int[]{nums[lIdx]};
        }

        int midIdx = (lIdx + rIdx) / 2;
        int[] lArr = sortArray(nums, lIdx, midIdx);
        int[] rArr = sortArray(nums, midIdx + 1, rIdx);
        return mergeArr(lArr, rArr);
    }

}
